#ifndef LISTA_H_
#define LISTA_H_
#include <cstdlib>
#include <exception>
#include "Iterador.h"

template <class TIPO>
struct No
{
	TIPO Valor;
	No *prox;
	No(TIPO v, No *p=NULL)
	{
		Valor = v;
		prox = p;
	}
	No()
	{
		prox=NULL;
	}
};

template <class TIPO>
class Lista : public Iterador<TIPO>
{
protected:
	No<TIPO> *inicio, *final, *cursor;


	No<TIPO> *SelecionaNo(int pos)
	{
		No<TIPO> *tmp=inicio;
		int cont=0;
		while(tmp!=NULL)
		{
			if(pos == cont)
				return tmp;
			cont++;
			tmp=tmp->prox;
		}
		return tmp;
	}

	No<TIPO> *InsereNo(No<TIPO> *no_ant, TIPO v)
	{

		No<TIPO> *novo = new No<TIPO>(v);
		if (no_ant == NULL) return novo;
		novo->prox = no_ant->prox;
		no_ant->prox = novo;
		return novo;
	}

	void RemoveNo(No<TIPO> *no_ant)
	{
		if(no_ant == NULL) return;
		No<TIPO> *tmp = no_ant->prox;
		no_ant->prox=tmp->prox;
		if(tmp->prox == NULL) return;
		delete tmp;

	}


public:

	Lista()
	{
		inicio=final=NULL;
	}
	virtual ~Lista()
	{
		while(inicio!=NULL)
		{
			RemoveNo(inicio);
		}
		delete inicio;
	}
	bool Vazio()
	{
		return(inicio==NULL);
	}
	void InsereFinal(TIPO v)
	{
		No<TIPO> *tmp=InsereNo(final, v);
		if(inicio==NULL)
			inicio=tmp;
		final=tmp;
	}
	void Insere(TIPO val, int pos)
	{
		No<TIPO> *tmp=SelecionaNo(pos);
		if(tmp==NULL)
			return;
		InsereNo(tmp);
	}

	void Remove(int pos)
	{
		No<TIPO> *tmp=SelecionaNo(pos);
		if(tmp==NULL)
			return;
		RemoveNo(tmp);
	}

	TIPO Seleciona(int pos)
	{
		No<TIPO> *tmp=SelecionaNo(pos);
		if(tmp==NULL)
			throw std::exception();
		return tmp->Valor;
	}

	int Pesquisa(TIPO v)
	{
		No<TIPO> *tmp=inicio;
		int cont=0;
		while(tmp!=NULL)
		{
			if(tmp->Valor==v)
			{
				return cont;
			}
			tmp=tmp->prox;
			cont++;
		}
		return-1;
	}


	int Tamanho()
	{
		int cont = 0;
		No<TIPO> *tmp = inicio;
		while(tmp != NULL)
		{
			tmp = tmp->prox;
			cont++;
		}
		return cont;
	}

	virtual void Primeiro() { cursor = inicio;}
	virtual void Proximo() { if(cursor != NULL) cursor = cursor->prox; }
	virtual bool Final() { return ( cursor == final); }
	virtual TIPO GetItem()
	{
		if(cursor == NULL)
			throw std::exception();
		return cursor->Valor;
	}


};

#endif /* LISTA_H_ */
